package Leetcode第二期;

import java.util.HashSet;
import java.util.Set;

/**
 * @author : K k
 * @date : 10:17 2020/10/17
 */
public class N皇后II_52 {

    //判断斜线左下
    static Set<Integer> bias1 = new HashSet<>();
    //右下
    static Set<Integer> bias2 = new HashSet<>();
    //判断列
    static Set<Integer> column = new HashSet<>();
    public int totalNQueens(int n) {
        //构造棋盘
        return dfsSolver(0, n, column, bias1, bias2);
    }
    //HashSet回溯剪枝
    private int dfsSolver(int index, int n, Set<Integer> column, Set<Integer> bias1, Set<Integer> bias2) {
        if (index == n) {
           return 1;
        }
        int count=0;
        for (int i = 0; i < n; i++) {
            //n行
            if (column.contains(i)) {
                continue;
            }
            //判断左下角
            int bia1 = index - i;
            if (bias1.contains(bia1)) {
                continue;
            }
            //判断左下角
            int bia2 = index + i;
            if (bias2.contains(bia2)) {
                continue;
            }
            column.add(i);
            bias1.add(bia1);
            bias2.add(bia2);
            count+=dfsSolver(index + 1, n, column, bias1, bias2);
            column.remove(i);
            bias1.remove(bia1);
            bias2.remove(bia2);
        }
        return count;
    }

    //
    public int totalNQueensA(int n) {

        return 1;
    }


    //在索引值范围且该位置不是皇后
    boolean isArea(boolean[][] chess, int n, int i, int j) {
        return i >= 0 && i < n && j >= 0 && j < n && !chess[i][j];
    }

    public static void main(String[] args) {
        int x=15;
        System.out.println((x&-x));
    }

}
